package algorithms;

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class K_Means {
	private int NUM;					// Number of features in each line or for each items.
	private int K;						// Parameter K.
	private Vector<double []> data;		// Data.
	private int [] labels; 				// array to store cluster label or result for each data item.
	private Vector<double []> centers;	// array to store k cluster centeroid.
	
	public K_Means(int inputK, int feature_num) {
		NUM = feature_num;
		K = inputK;
		data = new Vector<double []>();
		centers = new Vector<double []>();
	}
	
	public void input(String fileName){	
		Pattern p = Pattern.compile("[,\\s]+");	//regular expression. "," or multiple spaces;
		try{
			String line;
			FileInputStream fin =  new FileInputStream(fileName);
	        BufferedReader bufReader = new BufferedReader(new InputStreamReader(fin));
	        
	        while (( line = bufReader.readLine()) != null) {
	        	String temp[] = p.split(line);
	        	double item[] = new double[NUM];
	        	
	        	for(int j=0; j<temp.length; j++){
	        		double k = Double.valueOf(temp[j]).doubleValue();
	        		item[j] = k;
	        	}
	        
	        	data.add(item);
	        }
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	// Train model on training data set.
	public void train() {	
		labels = new int[data.size()];
		
		for(int i=0; i<data.size(); i++) {
			labels[i] = -1;
		}
		
		long seed = System.currentTimeMillis();		// set random seed;
		Random rand = new Random(seed);				
		
		Hashtable initCenters = new Hashtable();
		int numOfCenters = K;
		
		for(int i=0; i<numOfCenters; i++) {
			int temp = rand.nextInt(data.size());
			
			while(initCenters.containsValue(temp)) {
				temp = rand.nextInt(numOfCenters);
			} 
			
			initCenters.put(i, temp);
		}
		
		for(int i=0; i<numOfCenters; i++) {	// used to debug.
			System.out.println("key="+i+" || value="+initCenters.get(i));
		}
		
		
		
		for(int i=0; i<K; i++) {	//Initialize the centers vector.
			double temp[] = new double[NUM];
			
			for(int j=0; j<NUM; j++) {
				temp[j] = 0.0;
			}
			
			centers.add(temp);
		}
		
		int flag=0;						// flag indicates whether the cluster assignment is changed.
		int count[] = new int[K]; 		// count the number of items for each cluster.
		double tempCenters[][] = new double[K][NUM];	// temp store the info of centers.
		
		while(true) {    	// change the true to some terminate conditions in the future ????
			flag = 0;		
			double minDist = -1.0;	// Min distance.
			int la = -1;			// la indicates which cluster the data item belongs to.
	
			for(int m=0; m<K; m++) {		// initialize the array.
				count[m] = 0; 
			}
			
			for(int i=0; i<K; i++) {		// set each element in the tempCenters to zero.
				for(int j=0; j<NUM; j++) {
					tempCenters[i][j] = 0.0; 
				}
			}
			
			for(int i=0; i<data.size(); i++) {		// for each data item.
				double item[] = data.get(i);
				minDist = -1.0;				
				la = -1;						

				for(int j=0; j<K; j++) {			// for each cluster center.
					int clusterIndex = (int)(initCenters.get(j));
					double dist = this.getEucDist(item, data.get(clusterIndex));
					
					if(minDist>=0.0 && dist<minDist && dist>=0.0) {
						minDist = dist;
						la = j;
					} else if(minDist<0.0) {
						minDist = dist;
						la = j;
					}
				}
				
				if(labels[i]!=la) {
					flag++;
				}
				
				labels[i] = la;
				count[la]++;
				
				for(int k=0; k<NUM; k++) {
					//(centers.get(labels[i]))[k] += item[k];
					tempCenters[labels[i]][k] += item[k];
				}
			}
			
			for(int p=0; p<K; p++) {				// update centers by computing the mean value for each center point.
				for(int q=0; q<NUM; q++) {
					//(centers.get(p))[q] /= (1.0*count[p]);
					tempCenters[p][q] /= (1.0*count[p]);
				}
			}
			
			if(flag == 0) {		// centers are not changed. (terminate conditions)
				break;
			} else {			// centers are changed.
				for(int i=0; i<K; i++) {
					for(int j=0; j<NUM; j++) {
						(centers.get(i))[j] = tempCenters[i][j];
					}
				}
			}
		}
		
		////////////////////////////////////////////////////////////////////////////
		
		//print out centers. used to debug.
		for(int l=0; l<centers.size(); l++) {
			System.out.print("\ncenter: ");
			
			for(int k=0; k<NUM; k++) {
				System.out.print((centers.get(l))[k]+" ");
			}
			
			System.out.println("\n--------------------------");
			System.out.println("class_"+l+": ");
			
			for(int j=0; j<data.size(); j++) {
				int labl = labels[j];
				
				if(labl == l) {
					System.out.print("\t");
					for(int m=0; m<NUM; m++) {
						System.out.print((data.get(j))[m]+" ");
					}
					System.out.println("\n\t##########");
				}
			}
						
		}
	}
	
	// Do prediction on test data set.
	public void predict(String fileName) {			
		// read data from file.
		
		// predict the cluster each input point belongs to.
	}
	
	public void outputModel(String fileName) {	// output cluster centers to file.
		try {
			FileWriter fwriter = new FileWriter(fileName);
			BufferedWriter bufWriter = new BufferedWriter(fwriter);
			
			for(int i=0; i<centers.size(); i++) {
				String temp = ""+(centers.get(i))[0];
				for(int j=1; j<NUM; j++) {
					temp = temp + " " + ((centers.get(i))[j]);
				}
				
				bufWriter.write(temp+"\n");
			}
			
			bufWriter.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
	
	// a method to shuffle an array.
	public void shuffle(int a[]) {
		long seed = System.currentTimeMillis();
		Random rand = new Random(seed);

		// Shuffle by exchanging each element randomly
		for (int i=0; i<a.length; i++) {
			
			int randPos = rand.nextInt(a.length);
			System.out.print("rand position: "+randPos+" || ");
			
			for(int j=0; j<a.length; j++) {
				System.out.print(a[j]+" ");
			}
			
			System.out.println();
			
		    
		    int temp = a[i];
		    a[i] = a[randPos];
		    a[randPos] = temp;
		}
		
		for(int i=0; i<a.length; i++) {
			System.out.print(a[i] + " ");
		}
		
		System.out.println();
	}
	
	// get the Euclidean distance of two items.
	private double getEucDist(double a[], double b[]) {		
		if(a.length != b.length) {
			System.out.println("Number of features are different.");
			return -1.0;
		}
		
		// the process below may be optimized using java threads ??????
		int len = a.length;
		double sqDist = 0.0;
		
		for(int i=0; i<len; i++) {
			sqDist += (a[i]-b[i]) * (a[i]-b[i]);
		}
		
		double dist = Math.sqrt(sqDist);
		return dist;
	}
	
	//////////////////////////////////////////////////////
	public static void main(String[] args) {	//used to debug.
		
		File f = new File(".");
		try {
			System.out.println(f.getCanonicalPath());
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		K_Means km = new K_Means(2, 2);
		km.input("data/matlab_data.txt");
		km.print();
		System.out.println("||||||||||||||||||||||||||||||||||||||");
		km.train();
		km.outputModel("model.txt");
	}
	
	//////////////////////////////////////////////////////
	// The following methods are used to debug.
	
	public void print() {	//used to debug.
		for(int m=0; m<data.size(); m++) {
			System.out.print("line_"+(m+1)+": ");
			for(int n=0; n<(data.get(m)).length; n++) {
				double temp[] = data.get(m);
				System.out.print(temp[n]+" ");
			}
			
			System.out.println(" ");
		}
	}
	
	///////////////////////////////////////////////////////
	
}
